The present invention relates to protocols suitable for use with interconnection circuitry, and more particularly to methods and apparatus for transferring data in a computer system having a plurality of data sources interconnected in the form of a ring, and for determining topology of interconnection, and determining information about each node.
A typical computer system comprises a number of components, each performing a particular function. For example, such a system might include a central processing unit, a random access memory, a frame buffer memory, output control and timing circuitry, an output display, and input/output circuitry. Those skilled in the art will recognize that this list is merely illustrative, and that many other types of components might also be incorporated into the system.
In a typical system as described, it is often necessary for data to be transferred from one component to another. Traditionally, this has been accomplished by connecting each of the system components to a plurality of conductors referred to as a system bus which may include an address bus, a data bus, and one or more control lines. In operation, a component such as the central processing unit transmits data to another component by placing the address to which the data is directed on the system address bus, and the data on the system data bus. While it is convenient to think of the data and addresses as numbers, in actuality they exist on the bus in the form of electrical signals which are imposed on the bus by the transmitting component, and sensed by all remaining components attached to the bus. Because these signals generally change with each new bus transaction, it is important that components not sense them before they have fully reached the values corresponding to the data and address for the next transaction. To implement this requirement, one or more control signals may be dedicated to indicating when the data and address on the bus are valid. In addition, another control signal or signals may provide information about the transaction, such as whether it is a read or write operation, and whether it is a memory or an input/output operation.
Returning to the scenario in which data and a corresponding address has been placed on the bus, the component for which the data is destined recognizes an address on the address bus within its range of addresses and accepts the data available on the data bus. All other components, recognizing that the address is not one of theirs, ignore the data and control signals on the bus.
Since each of the address and data buses is made up of a number of conductors which physically connect to each of the system components on the bus and all of the conductors of each bus carry the information that is being directed to one address, it is a characteristic of this system that during the time that any particular source of information is utilizing the buses, the buses are unavailable for use by any other source. Consequently, data may be sent by only one source at a time (although more than one destination may receive data if more than one destination can respond to the same address) since there is no room for information from more than one source at a time on the data or address buses.
In order to overcome the limits of a bus system, alternative methods of interconnection have been proposed which permit a plurality of component pairs to exchange data simultaneously. One such arrangement is a ring-type system, in which all components which would normally be connected to a bus are connected to only two other components in a unidirectional ring. Each component receives information from a first neighboring component on an "upstream" port, and sends information to a second neighboring component on a "downstream" port. Each component then forwards information around the ring until the information arrives at its destination, at which time the destination node, rather than sending the information further "downstream," gives the information to its associated component. Separating the interconnection into individual paths between components isolates the components from all but two other components but increases the amount of traffic which can be handled by the ring over the amount which may be placed on a system bus because a number of sources of information can communicate with a number of destinations at the same time. This occurs because the isolation allows one system component to send information to a second component while a third component sends information to a fourth component, and so on.
The ring interconnection architecture is typically used as a secondary connection between the components of a computer system. The primary connection between these components is usually a busing arrangement such as the NuBus manufactured and used by Apple Computer, Inc., in its line of Apple Macintosh II personal computers.
While a ring interconnection architecture provides the capability for a computer system to move data from one or more source nodes to one or more corresponding destination nodes, it does not inherently define a mechanism whereby a component associated with the destination node knows what to do with the received information. Such a mechanism, or protocol, is necessary in a computer system which typically interconnects a number of very different devices, each having individually defined interface operations.
Protocols exist for transferring information on computer networks. However, these existing protocols are inappropriate for conveying information in a ring interconnection architecture which is intended for use as a bus substitute [or supplement] for a number of reasons. To begin with, networking protocols are symmetric, in that the communicating devices must each be capable of performing complicated operations defined by the protocol. Thus, no allowances are made for communications between an intelligent device and a simple device having a simple architecture which is responsive to commands sent by the intelligent device.
Networking protocols are also inappropriate for connecting devices of various complexity because they require an intelligent bridge (usually called a router). Without this intelligent bridge, networking protocols will only function on a local network.
Another aspect of networking protocols which makes them inappropriate in the above-described ring interconnect architecture is the fact that these protocols shield the actual addressing and architecture of network components from one another. Thus, physical addresses of resources within a network component are not visible to any other network component. Consequently, access to such resources requires the mediation of intelligent software in the local node. Because the data arrives at the node without a map to physical addressing, it is often buffered so that the local processor can apply the protocol to the data and then move the data to the appropriate final location. This requirement limits the performance of the node to the performance of a processor running software and performing memory copies.
Additionally, network protocols often rely on broadcast capabilities (a message with one source and all other nodes as destination). However, not all of the contemplated ring interconnect architectures support this method of communication. Consequently, these types of network protocols would not function in the desired environment.
Another reason why existing network protocols are inappropriate for use in the above-described ring interconnect architecture is that these existing protocols typically will not operate without a significant amount of processor power, support hardware or both. This may be too large an investment for some low cost ring interconnection architectures.